際際滷

際際滷Share a Scribd company logo

Roots of polynomials

M
Maria Fernanda

This document discusses methods for finding the roots of polynomial equations, including Muller's method, Bairstow's method, and the Bairstow algorithm. It provides details on how each method works, such as deriving the coefficients of a parabola through three points for Muller's method or using synthetic division and solving simultaneous equations to estimate changes in values for Bairstow's method. An example is also shown applying Bairstow's method to find the roots of a 5th order polynomial equation.

1 of 21
Download to read offline
Maria Fernanda Vergara Mendoza Petroleum Engineering UIS-COLOMBIA
In this chapter, you will learn some methods to find the roots of polynomial equations of the general form: Where n= the order of the polynomial; a= constant coefficients. RULES: For an nth-order equation, there are n real or complex roots. If n is odd, there is at least one real root The complex roots exsist in conjugate pairs (a+bi and a-bi), i=(-1)
珂顎鉛鉛艶姻s Bairstows Method Method
The 珂顎鉛鉛艶姻s method, is like the secant method, just that this one projects a parabola through three points unlike secant method, who projects a straight line. This method consists of deriving the coefficients of the parabola that goes through the three points.
Write the parabolic equation in this form: P( x) a( x xi 1 ) 2 b( x xi 1 ) c The coefficients a, b, and c can be evaluated by substituting each of the three points to give: f ( xi 1 ) a( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) c f ( xi ) a( xi xi 1 ) 2 b( xi xi 1 ) c f ( xi 1 ) a( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) c
Two of the terms of f ( xi 1 ) are zero, it can be solved for c=f(xi+1). f ( xi 1 ) f ( xi 1 ) a ( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) f ( xi ) f ( xi 1 ) a ( xi xi 1 ) 2 b( xi xi 1 ) Using algebraic manipulations, we solve the remaining coefficients: hi 1 xi xi 1 hi xi 1 xi f ( xi ) f ( xi 1 ) i 1 xi xi 1 f ( xi 1 ) f ( xi ) i xi 1 xi
These can be substituted to give: (hi 1 hi )b (hi 1 hi ) 2 a hi 1 i 1 hi i 2 hi b hi a hi i The results can be summarized as i i 1 a b ahi i c f ( xi 1 ) hi hi 1 Once you know the approximate coefficients you have to find the approximated root using the quadratic equation : 2c xi 2 xi 1 b b 2 4ac
The error can be calculated as: There is a problem with xi 2 equation, this equation yields two roots, in this method the sign is chosen with this strategies: 1. If only real roots are being located, we choose the two original points that are nearest the new root estimate, xi+2 . If both real and complex roots are being evaluated, a sequential approach is employed. That means: xi, xi+1, xi+2 take the place of xi-1, xi, xi+1
If you have as initial values xi 1 4.5 xi 5 .5 xi 1 5 respectively, find the root of the equation: f ( x) x 3 13x 12 FIRST: Evalue the equation in its initial values f (4.5) 20.625 f (5.5) 82.875 f (5) 48
SECOND: This values are used to calculate: hi 1 5 . 5 4 .5 1 hi 5 5 .5 0 .5 82.875 20.625 i 1 62.25 5 . 5 4 .5 48 82.875 i 69.75 5 5.5 THIRD: Find the a, b, c coefficients: 69.75 62.25 a 15 0 .5 1 b 15( 0.5) 69.75 62.75 c 28
2(48) xi 2 5 3.976487 62.25 31.54451 The error is: 1.023513 a 100% 25.74 3.976487 This is a huge error, so its necesary to do other iterations: xi 1 5 .5 xi 5 xi 1 3.976487 Repeat the calculations and get a low percent of error: Iteration Xr Ea% 0 5 -- 1 3.976487 25.74 2 4.00105 0.6139 3 4 0.0262 4 4 0.0000119
Is an iterative approach related loosely to both the Muller and Newton Raphson methods. It is based on the idea of synthetic division of the given polynomial by a quadratic function and can be used to find all the roots of a polynomial. The idea is to do a synthetic division of the polynomial Pn(x) by the quadratic factor (x2 - rx - s).
The synthetic division can be extended to quadratic factors: Pn ( x) ( x 2 rx s)Qn 2 ( x) R x 2 rx s bn x n 2 bn 1 x n 3 ... b3 x b2 residue residue b1 ( x r ) ... b0 When you multiply and match factors have: an bn 1 bn an an 1 bn 1 rbn bn 1 an 1 rbn an 2 bn 2 rbn 1 sbn bn 2 an 2 rbn 1 sbn an 3 bn 3 rbn 2 sbn 1 bn 3 an 3 rbn 2 sbn 1 : : a1 b1 rb2 sb3 b1 a1 rb2 sb3 a0 b0 rb1 sb2 b0 a0 rb1 sb2
The idea is to find values of r and s, making b1 and b0 zero. The method works taking an initial approach (r0, s0) and getting better approaches (rk, sk), this is an iterative procedure, the process ends when the residue of dividing the polynomial by (x2 - rkx - sk) its zero. B1=f(s, r) B0=g(s, r)
Because both bo and b1 are functions of both r and s, they can be expanded using a Taylor series: b1 b1 b1 (r r, s s ) b1 r s r s b0 b0 b0 (r r, s s ) b0 r s r s The changes, r and s, can be estimated by setting the expansion equal to zero: b1 b1 b1 r s r s b0 b0 b0 r s r s
If the partial derivatives of the bs can be determined, these are a system of two equations that can be solved simultaneously for the two unknowns, r and s. According to Bairstow, the partial derivatives can be obtained by a synthetic division of the bs. cn bn cn 1 bn 1 rcn cn 2 bn 2 rcn 1 scn : cn k bn k rcn ( k 1) scn ( k 2)
b1 b2 b b1 b2 b r b2 s 3 c2 r b3 s 3 c3 r r r s s s b0 b b b0 b b r 1 b1 s 2 c1 r 0 b2 s 2 c2 r r r s s s Then the system of equations can be written as: c2 r c3 s b1 c1 r c2 s b0
APPROXIMATED ERROR r s a ,r .100% a,s .100% r s When both of these error estimates fall below a stopping criterion, the values of the roots can be determined by: r r 2 4s x 2
Employ Bairstows method to determine the roots of the polynomial f 5 ( x) x5 3.5x 4 2.75x3 2.125x 2 3.875x 1.25 Use initial guesses of r=s=-1 and iterate to a level of tolerance of 1% SOLUTION: b5=1 b4=-4.5 b3=6.25 b2=0.375 b1=-10.5 b0=11.375 c5=1 c4=-5.5 c3=10.75 c2=-4.875 c1=-16.375 Thus, the simultaneous equations to solve r and s are: 4.875 r 10.75 s 10.5 16.375 r 4.875 s 11.375
Which can be solved for r=0.3558 and s=1.1381. r=-0.6442 S=0.1381 And the approximate errors are: 0.3558 1.1381 a ,r .100% 55.23% a,s .100% 824.1% 0.6442 0.1381 The computation can be continued with the result that after four iterations the metod converges on velues of r=-0.5 and s=0.5 0.5 ( 0.5) 2 4(0.5) x 0.5, 1 2
CHAPRA, Steven C. Numerical methods for engineers, Fifth edition. Mc Graw Hill. CARRILLO, Eduardo. Raices de polinomios. PPT.

More Related Content

Roots of polynomials

  • 1. Maria Fernanda Vergara Mendoza Petroleum Engineering UIS-COLOMBIA
  • 2. In this chapter, you will learn some methods to find the roots of polynomial equations of the general form: Where n= the order of the polynomial; a= constant coefficients. RULES: For an nth-order equation, there are n real or complex roots. If n is odd, there is at least one real root The complex roots exsist in conjugate pairs (a+bi and a-bi), i=(-1)
  • 3. 珂顎鉛鉛艶姻s Bairstows Method Method
  • 4. The 珂顎鉛鉛艶姻s method, is like the secant method, just that this one projects a parabola through three points unlike secant method, who projects a straight line. This method consists of deriving the coefficients of the parabola that goes through the three points.
  • 5. Write the parabolic equation in this form: P( x) a( x xi 1 ) 2 b( x xi 1 ) c The coefficients a, b, and c can be evaluated by substituting each of the three points to give: f ( xi 1 ) a( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) c f ( xi ) a( xi xi 1 ) 2 b( xi xi 1 ) c f ( xi 1 ) a( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) c
  • 6. Two of the terms of f ( xi 1 ) are zero, it can be solved for c=f(xi+1). f ( xi 1 ) f ( xi 1 ) a ( xi 1 xi 1 ) 2 b( xi 1 xi 1 ) f ( xi ) f ( xi 1 ) a ( xi xi 1 ) 2 b( xi xi 1 ) Using algebraic manipulations, we solve the remaining coefficients: hi 1 xi xi 1 hi xi 1 xi f ( xi ) f ( xi 1 ) i 1 xi xi 1 f ( xi 1 ) f ( xi ) i xi 1 xi
  • 7. These can be substituted to give: (hi 1 hi )b (hi 1 hi ) 2 a hi 1 i 1 hi i 2 hi b hi a hi i The results can be summarized as i i 1 a b ahi i c f ( xi 1 ) hi hi 1 Once you know the approximate coefficients you have to find the approximated root using the quadratic equation : 2c xi 2 xi 1 b b 2 4ac
  • 8. The error can be calculated as: There is a problem with xi 2 equation, this equation yields two roots, in this method the sign is chosen with this strategies: 1. If only real roots are being located, we choose the two original points that are nearest the new root estimate, xi+2 . If both real and complex roots are being evaluated, a sequential approach is employed. That means: xi, xi+1, xi+2 take the place of xi-1, xi, xi+1
  • 9. If you have as initial values xi 1 4.5 xi 5 .5 xi 1 5 respectively, find the root of the equation: f ( x) x 3 13x 12 FIRST: Evalue the equation in its initial values f (4.5) 20.625 f (5.5) 82.875 f (5) 48
  • 10. SECOND: This values are used to calculate: hi 1 5 . 5 4 .5 1 hi 5 5 .5 0 .5 82.875 20.625 i 1 62.25 5 . 5 4 .5 48 82.875 i 69.75 5 5.5 THIRD: Find the a, b, c coefficients: 69.75 62.25 a 15 0 .5 1 b 15( 0.5) 69.75 62.75 c 28
  • 11. 2(48) xi 2 5 3.976487 62.25 31.54451 The error is: 1.023513 a 100% 25.74 3.976487 This is a huge error, so its necesary to do other iterations: xi 1 5 .5 xi 5 xi 1 3.976487 Repeat the calculations and get a low percent of error: Iteration Xr Ea% 0 5 -- 1 3.976487 25.74 2 4.00105 0.6139 3 4 0.0262 4 4 0.0000119
  • 12. Is an iterative approach related loosely to both the Muller and Newton Raphson methods. It is based on the idea of synthetic division of the given polynomial by a quadratic function and can be used to find all the roots of a polynomial. The idea is to do a synthetic division of the polynomial Pn(x) by the quadratic factor (x2 - rx - s).
  • 13. The synthetic division can be extended to quadratic factors: Pn ( x) ( x 2 rx s)Qn 2 ( x) R x 2 rx s bn x n 2 bn 1 x n 3 ... b3 x b2 residue residue b1 ( x r ) ... b0 When you multiply and match factors have: an bn 1 bn an an 1 bn 1 rbn bn 1 an 1 rbn an 2 bn 2 rbn 1 sbn bn 2 an 2 rbn 1 sbn an 3 bn 3 rbn 2 sbn 1 bn 3 an 3 rbn 2 sbn 1 : : a1 b1 rb2 sb3 b1 a1 rb2 sb3 a0 b0 rb1 sb2 b0 a0 rb1 sb2
  • 14. The idea is to find values of r and s, making b1 and b0 zero. The method works taking an initial approach (r0, s0) and getting better approaches (rk, sk), this is an iterative procedure, the process ends when the residue of dividing the polynomial by (x2 - rkx - sk) its zero. B1=f(s, r) B0=g(s, r)
  • 15. Because both bo and b1 are functions of both r and s, they can be expanded using a Taylor series: b1 b1 b1 (r r, s s ) b1 r s r s b0 b0 b0 (r r, s s ) b0 r s r s The changes, r and s, can be estimated by setting the expansion equal to zero: b1 b1 b1 r s r s b0 b0 b0 r s r s
  • 16. If the partial derivatives of the bs can be determined, these are a system of two equations that can be solved simultaneously for the two unknowns, r and s. According to Bairstow, the partial derivatives can be obtained by a synthetic division of the bs. cn bn cn 1 bn 1 rcn cn 2 bn 2 rcn 1 scn : cn k bn k rcn ( k 1) scn ( k 2)
  • 17. b1 b2 b b1 b2 b r b2 s 3 c2 r b3 s 3 c3 r r r s s s b0 b b b0 b b r 1 b1 s 2 c1 r 0 b2 s 2 c2 r r r s s s Then the system of equations can be written as: c2 r c3 s b1 c1 r c2 s b0
  • 18. APPROXIMATED ERROR r s a ,r .100% a,s .100% r s When both of these error estimates fall below a stopping criterion, the values of the roots can be determined by: r r 2 4s x 2
  • 19. Employ Bairstows method to determine the roots of the polynomial f 5 ( x) x5 3.5x 4 2.75x3 2.125x 2 3.875x 1.25 Use initial guesses of r=s=-1 and iterate to a level of tolerance of 1% SOLUTION: b5=1 b4=-4.5 b3=6.25 b2=0.375 b1=-10.5 b0=11.375 c5=1 c4=-5.5 c3=10.75 c2=-4.875 c1=-16.375 Thus, the simultaneous equations to solve r and s are: 4.875 r 10.75 s 10.5 16.375 r 4.875 s 11.375
  • 20. Which can be solved for r=0.3558 and s=1.1381. r=-0.6442 S=0.1381 And the approximate errors are: 0.3558 1.1381 a ,r .100% 55.23% a,s .100% 824.1% 0.6442 0.1381 The computation can be continued with the result that after four iterations the metod converges on velues of r=-0.5 and s=0.5 0.5 ( 0.5) 2 4(0.5) x 0.5, 1 2
  • 21. CHAPRA, Steven C. Numerical methods for engineers, Fifth edition. Mc Graw Hill. CARRILLO, Eduardo. Raices de polinomios. PPT.